/*
 *	给定一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。设计两种算法，时间复杂度为O(n)和O(nlogn)。
 */

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>

using namespace std;

int x = 18;
int a[]={2,3,4,9,0,7,8,6,1,5};
int n = sizeof(a)/sizeof(a[0]);

/* the time complexity is O(n)*/
int f(int *array,int n)
{
	int i , j ;
	i=0,j=n-1;
	while(i<j)
	{
		if(array[i]+array[j]<x) 
		{
			i++; 
			continue;
		}
		else if(array[i]+array[j]>x)
		{
			j--;
			continue;
		}
		else
		{
			return 1;
		}
	}
	return 0;
}

/* binary_search */
int binary_search(int m)
{
	int min = 0 , max = n-1;
	int	mid = (max-min)/2+min;
	while(min<max)
	{
		mid = (max-min)/2+min;
		if(a[mid] ==  m) return 1;
		else if(mid>m) max = mid-1;
		else min = mid+1;
	}
	return 0;
}

/* the time complexity is O(nlogn) */
int f1(int *array,int n)
{
	int m;
	for(int i=0;i<n;i++)
	{
		m = x - a[i];
		if( binary_search(m) )
		{
			return 1;
		}
		else continue;
	}
	return 0;
}

int main()
{
	sort(a,a+n);
	if( f(a,n) ) 
	{
		cout<<"Found"<<endl;
	}
	else cout<<"Not Found"<<endl;
	if( f1(a,n) )
	{
		cout<<"Found"<<endl;
	}
	else cout<<"Not Found"<<endl;
	return 0;
}
